题意
树上有一些碎片，每次可以选择两个距离大于1的碎片在它们的最短路径上分别靠近一格，最终使得它们聚在任意一点
求最小的步数或告知不可能
题解
对于一整棵树，如果根节点的所有子节点到它的距离和为偶数
且子树中到根距离和最大值不大于这棵整棵树到根的距离和的1/2，就是可行的
注：等价于这个问题，有{\(a_i\)}，每次选择两个数各减去1，使最终和最小
如果\(2Max>sum\)，最少距离和为\(2Max-sum\)，否则与原sum的奇偶性相同（0或1）
因此每次要递归地尽量把到根距离和最大的子树的和变得最小
调试记录
真的是做了整整一个晚上机房好吵啊
用sdep[v]算到根的距离和没有考虑v是否也对距离和有贡献（s[v]==‘1’）1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
const int INF = 0x3f3f3f3f3f3f;
const int maxn = 2005;
using namespace std;
struct E{
int to, nxt;
}e[maxn << 1];
int head[maxn], tot = 0;
void addedge(int u, int v){
e[++tot].to = v, e[tot].nxt = head[u];
head[u] = tot;
}
int dep[maxn], sz[maxn], sdep[maxn], sum; char s[maxn];
void dfs1(int cur, int fa){
dep[cur] = dep[fa] + 1;
sum += (dep[cur] - 1) * (s[cur] == '1');
for (int i = head[cur]; i; i = e[i].nxt){
int v = e[i].to;
if (v != fa){
dfs1(v, cur);
sz[cur] += sz[v] + (s[v] == '1');
sdep[cur] += sdep[v] + sz[v] + (s[v] == '1');
}
}
}
void dfs2(int cur, int fa){
int link = 0;
for (int i = head[cur]; i; i = e[i].nxt){
int v = e[i].to;
if (v == fa) continue;
if (sdep[v] + sz[v] + (s[v] == '1') > sdep[link] + sz[link] + (s[link] == '1') || link == 0) link = v;
}
if (link == 0) return;
dfs2(link, cur); sdep[cur] = 0;
for (int i = head[cur]; i; i = e[i].nxt)
if (e[i].to != fa) sdep[cur] += sdep[e[i].to] + sz[e[i].to] + (s[e[i].to] == '1');
if (2ll * (sdep[link] + sz[link] + (s[link] == '1')) > sdep[cur]) sdep[cur] = 2ll * (sdep[link] + sz[link] + (s[link] == '1')) - sdep[cur];
else sdep[cur] = sdep[cur] & 1;
}
int n, ans = INF;
signed main(){
scanf("%lld%s", &n, s + 1);
for (int u, v, i = 1; i < n; i++){
scanf("%lld%lld", &u, &v);
addedge(u, v); addedge(v, u);
}
for (int rt = 1; rt <= n; rt++){
memset(dep, 0, sizeof dep); memset(sz, 0, sizeof sz); sum = 0;
memset(sdep, 0, sizeof sdep);
dfs1(rt, 0); if (sum & 1) continue;
dfs2(rt, 0);
if (sdep[rt] == 0) ans = min(ans, sum >> 1);
}
if (ans == INF) ans = -1;
printf("%lld\n", ans);
return 0;
}